/*
 * @lc app=leetcode.cn id=35 lang=javascript
 *
 * [35] 搜索插入位置
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    if (target > nums[nums.length - 1]) {
        return nums.length
    }
    let startIndex = 0, endIndex = nums.length - 1, middleIndex = null;
    while(startIndex < endIndex) {
        middleIndex  = (startIndex + endIndex) >> 1
        if(nums[middleIndex] === target) {
            return middleIndex
        }
        if (nums[middleIndex] > target) {
            endIndex = middleIndex
        }
        if (nums[middleIndex] < target) {
            startIndex = middleIndex
        }
        if (startIndex === endIndex) {
            return middleIndex
        }
        if (startIndex + 1 === endIndex) {
            // console.log('间隔1', startIndex, middleIndex, endIndex)
            if (target <= nums[startIndex]) {
                return startIndex
            }
            if (nums[startIndex] < target <= nums[endIndex]) {
                return endIndex
            }
            if (target > nums[endIndex]) {
                return endIndex + 1
            }
            return startIndex
        }
        // console.log(startIndex, middleIndex, endIndex)
    }
    return middleIndex
};
// @lc code=end

/* 
    二分查找
    应该是左右指针可以错位，我写的逻辑需要前后判断就很不简练
*/

